package _interview100;

/**
 * 74. 搜索二维矩阵
 */
public class No74 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int l1 = 0, r1 = matrix.length - 1;
        while (l1 <= r1) {
            int mid = l1 + (r1 - l1) / 2;
            if (matrix[mid][0] <= target) l1 = mid + 1;
            else r1 = mid - 1;
        }

        int i1 = l1 - 1;
        if (i1 == -1) return false;

        int l2 = 0, r2 = matrix[0].length - 1;
        while (l2 <= r2) {
            int mid = l2 + (r2 - l2) / 2;
            if (matrix[i1][mid] < target) l2 = mid + 1;
            else r2 = mid - 1;
        }
        return l2 != matrix[0].length && matrix[i1][l2] == target;
    }
}
